public class Solution {
    public int jumpFloor(int target) {

        // 递归
        /*
        if (target == 1)
            return 1;
        else if (target == 2)
            return 2;
        else 
            return jumpFloor(target - 1) + jumpFloor(target - 2);
        */

        // 动态规划
        /*
        int[] dp = new int[41];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
        */

        // 空间优化
        if (target < 3) 
            return target;
        int ret = 0;
        int a = 1;
        int b = 2;
        for (int i = 3; i <= target; i++) {
            ret = a + b;
            a = b;
            b = ret;
        }
        return ret;

    }
}
